/*
 * GRoundRobinMatchCreator.java
 * Created on 18 août 2007
 *
 * Glacéo Internet Platform
 * http://sourceforge.net/projects/chm/
 *
 * Copyright (c) 2005-2008, Jens und Jan Janke (VirtualHockey Project)
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.hockeo.vhbase.seasoncycle.services;


import java.util.List;
import java.util.Stack;

import com.hockeo.vhbase.data.dao.IGDao;
import com.hockeo.vhbase.data.dao.club.GClub;
import com.hockeo.vhbase.data.dao.contest.GRoundRobinContestElement;
import com.hockeo.vhbase.data.dao.match.GMatch;
import com.hockeo.vhbase.data.dao.season.GMatchday;
import com.hockeo.vhbase.error.GDataException;

/**
 * Creates matches for a round robin style tournament.
 *
 * @version $Id$
 * @author jjanke
 */
public class GRoundRobinMatchCreator
{
  private final IGDao               d_dao;
  private GRoundRobinContestElement d_contestElement;
  private List<GClub>               d_listClubs;
  private int                       d_nFirstMatchdayNum;

  /**
   * Initializes the match creator.
   *
   * @param dao the DAO to use for all database interactions.
   */
  public GRoundRobinMatchCreator( final IGDao dao )
  {
    d_dao = dao;
  }

  /**
   * Generates all matches for the given contest element according to its specification
   * (number of rounds and clubs etc.). The clubs participating in the matches must be
   * provided in a seperate list. This method does not check if there are already any
   * matches. So calling this method multiple times in a row for the same contest element
   * will result in the creation of unneccessary additional matches.
   *
   * @param contestElement the contest element for which to create matches
   * @param listClubs the clubs participating in the contest element
   * @return number of generated matches
   */
  public int generateMatches( final GRoundRobinContestElement contestElement, final List<GClub> listClubs )
  {
    d_contestElement = contestElement;
    d_listClubs = listClubs;

    try
    {
      // We determine the first matchday number since not in all elements, the first matchday has
      // the number 1. Especially in multi-round contests, this is not the case.
      //
      d_nFirstMatchdayNum = d_dao.findFirstMatchday( contestElement ).getNum() - 1;
    }
    catch ( GDataException ex )
    {
      throw new IllegalStateException( "No matchday is attached to the contest element " + contestElement.getId(), ex );
    }

    int[][] matrix = createMatchDayMatrix();

    matrix = balanceMatchDayMatrix( matrix );
    matrix = checkHomeAwayMatchesUnevenTeamNumber( matrix );

    return createMatchdays( matrix );
  }

  /**
   * Creates a quadratic matrix. The indexes represent the teams of the league. The
   * contents says on which match day the two teams (i,j) play against each other. This
   * method fills the matrix.
   *
   * @return the filled match day matrix
   */
  private int[][] createMatchDayMatrix()
  {
    int nTeams = d_listClubs.size();

    // add an artificial extra team, if the number of teams is uneven
    //
    if ( nTeams % 2 != 0 )
    {
      nTeams++;
    }

    // create empty matrix
    //
    int[][] matrix = new int[nTeams][nTeams];

    // fill matrix
    //
    for ( int i = 0; i < nTeams; i++ )
    {
      for ( int j = 0; j < nTeams; j++ )
      {
        // a team cannot play against itself
        //
        if ( i == j )
        {
          matrix[i][j] = -1;
        }
        // special treatment for the last column of the matrix
        //
        else if ( j == nTeams - 1 )
        {
          matrix[i][j] = ( j + 2 * i );
          while ( matrix[i][j] >= nTeams )
          {
            matrix[i][j] -= ( nTeams - 1 );
          }
        }
        // all other cells
        //
        else
        {
          // above the diagonale, only values from 1 to (nTeams - 1) are allowed
          //
          if ( j > i )
          {
            matrix[i][j] = i + j;
            while ( matrix[i][j] >= nTeams )
            {
              matrix[i][j] -= ( nTeams - 1 );
            }
          }
          // below the diagonale, only values from nTeams to (2 * (nTeams - 1)) are
          // allowed
          //
          else
          {
            matrix[i][j] = matrix[j][i] + nTeams - 1;
          }
        }
      }
    }

    return matrix;
  }

  /**
   * This methods balances the matrix in order to equally distribute home and away matches
   * over the season.
   *
   * @param matrix the initially filled match day matrix
   * @return the balanced match day matrix
   */
  private int[][] balanceMatchDayMatrix( int[][] matrix )
  {
    for ( int i = 0; i < matrix.length; i++ )
    {
      for ( int j = i + 1; j < matrix.length; j++ )
      {
        // exchange all uneven values with their complement from below the diagonale
        //
        if ( matrix[i][j] % 2 != 0 )
        {
          int tmp = matrix[i][j];
          matrix[i][j] = matrix[j][i];
          matrix[j][i] = tmp;
        }
      }
    }

    return matrix;
  }

  /**
   * <p>
   * If there is an uneven number of teams in the league, each team shall play an equal
   * number of matches at home and on the road per round. This method checks whether this
   * condition is respected and changes the match day allocation if necessary. This method
   * does not take care of the fact that a team should ideally play one game at home and
   * the next on the road etc. It just considers the total number of home and away games.
   * (it is assumed that the last index of the matrix represents the extra team which was
   * added because of the uneven total number of games).
   * </p>
   *
   * <p>
   * This method checks whether there is really an uneven number of teams, so no
   * precondition has to be respected prior to calling it.
   * </p>
   *
   * @param matrix a balanced match day matrix
   * @return matrix a balanced match day matrix in which all teams play an equal number of
   *         games at home and on the road per round if the total number of teams in the
   *         league is uneven
   */
  private int[][] checkHomeAwayMatchesUnevenTeamNumber( int[][] matrix )
  {
    int n = d_listClubs.size();

    // check if the number of teams is even (then return)
    //
    if ( n % 2 == 0 )
    {
      return matrix;
    }

    // stack to keep the teams with too many and not enough home games
    //
    Stack<Integer> tooManyHomeGames = new Stack<Integer>();
    Stack<Integer> notEnoughHomeGames = new Stack<Integer>();

    // array to count the number of found home games
    //
    int[] numHomeGames = new int[n];

    // expected number of home games
    //
    int expectedHomeGames = ( n - 1 ) / 2;

    // fill stack initially with all teams (they potentially do not have enough home
    // games)
    //
    for ( int i = 0; i < n; i++ )
    {
      notEnoughHomeGames.add( new Integer( i ) );
    }

    // count the number of home games for each team and add teams with too many home games
    // to the stack 'tooManyHomeGames'. Teams which do not have enough home games remain
    // in the stack 'notEnoughHomeGames'.
    //
    for ( int i = 0; i < n; i++ )
    {
      for ( int j = 0; j < n; j++ )
      {
        if ( i == j )
          continue;

        if ( matrix[i][j] <= n )
        {
          numHomeGames[i]++;

          if ( numHomeGames[i] == expectedHomeGames )
          {
            notEnoughHomeGames.remove( new Integer( i ) );
          }
          else if ( numHomeGames[i] > expectedHomeGames )
          {
            tooManyHomeGames.push( new Integer( i ) );
          }
        }
      }
    }

    // change home/away game assignment if necessary
    //
    while ( !tooManyHomeGames.isEmpty() )
    {
      int i = tooManyHomeGames.pop();
      int j = notEnoughHomeGames.pop();

      // search as long as there is a possible change combination (i.e. a pair of teams
      // i and j, where i has a home game against j
      //
      while ( matrix[i][j] > n )
      {
        notEnoughHomeGames.insertElementAt( new Integer( j ), 0 );
        j = notEnoughHomeGames.pop();
      }

      // exchange home/away assignment
      //
      int tmp = matrix[i][j];
      matrix[i][j] = matrix[j][i];
      matrix[j][i] = tmp;
    }

    return matrix;
  }

  /**
   * Analyses the games matrix and creates the complete schedule for the season.
   *
   * @param matchDao the DAO that is used to write generated matches to the database
   * @param matrix a balanced match day matrix
   * @return the number of generated matches
   */
  private synchronized int createMatchdays( int[][] matrix )
  {
    int numMatches = 0;

    int n = d_listClubs.size();
    int matchdaysPerRound = n - 1;

    // Uneven number of teams (we need to adjust the number of matchdays per round)
    //
    if ( n % 2 != 0 )
      matchdaysPerRound = n;

    for ( int i = 0; i < n; i++ )
    {
      for ( int j = 0; j < n; j++ )
      {
        if ( i == j )
          continue;

        int md = matrix[i][j];
        int rnd = ( md - 1 ) / matchdaysPerRound; // either 0 or 1
        int curRnd = 0;

        // adjust matchday number if it is higher than the number of matchdays per round
        //
        if ( rnd == 1 )
        {
          md = md - matchdaysPerRound;
        }

        // affect game to all necessary matchdays
        //
        while ( curRnd < d_contestElement.getNumRounds() )
        {
          if ( curRnd % 2 == rnd )
          {
            int nMatchdayNumber = ( curRnd * matchdaysPerRound ) + md;
            GMatchday matchday = d_contestElement.getMatchday( d_nFirstMatchdayNum + nMatchdayNumber );

            assert matchday != null : "Matchday is null for contest element " + d_contestElement.getId()
                + " matchday no. " + nMatchdayNumber;

            GMatch match = new GMatch( matchday, d_listClubs.get( i ), d_listClubs.get( j ) );

            // save the created match to the database
            //
            d_dao.makePersistent( match );

            numMatches++;
          }

          curRnd++;
        }
      }
    }

    return numMatches;
  }
}
